package com.markus.code.动态规划.硬币问题;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/14 23:15
 * todo: 零钱兑换问题
 */
public class LeetCode_322 {
    /**
     * 给定不同面额的硬币 coins 和一个总金额 amount。
     * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
     * 如果没有任何一种硬币组合能组成总金额，返回 -1
     */
    private int res = Integer.MAX_VALUE;

    public int coinChange1(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        //直接递归
        process1(coins, amount, 0);
        if (res == Integer.MAX_VALUE) {
            return -1;
        }
        return res;
    }

    /**
     * 先来看看直接暴力递归的做法：
     *      基础条件就是：来到当前递归，判断amount的情况
     *          amount < 0 : 当前不管做什么选择都不可能凑成amount直接返回
     *          amount = 0 : 当前不做选择，就是一种方案
     *          amount > 0 : 当前需要从硬币中选择可行方案来组成amount
     */
    private void process1(int[] coins, int amount, int count) {
        if (amount < 0) {
            return;
        }
        if (amount == 0) {
            res = Math.min(res, count);
        }
        for (int i = 0; i < coins.length; i++) {
            process1(coins, amount - coins[i], count + 1);
        }
    }

    private int[] memo;
    public int coinChange2(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        memo = new int[amount + 1];
        return process2(coins, amount);
    }
    /**
     * 暴力递归，会产生很多不必要计算的树，我们可以通过记忆化搜索来解决问题
     *      memo[n]数组表示 组成n元使用最少的硬币个数
     * 这次同样也是递归的形式，不过这个递归表示的直接是凑成amount钱数，所用的最少金币数量
     *      看看基础条件：
     *          amount < 0 : 说明前面做的选择是一条不可行的方案
     *          amount = 0 : 前面已经做完选择了，我不需要再挑选
     *
     */
    private int process2(int[] coins, int amount) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        //memo[amount]有三种取值方案：
        //          1、0：代表凑成该钱数使用的最少金币数量还未被计算
        //          2、-1 代表凑成该钱数使用的最少金币数量方案是不存在的
        //          3、具体种类数 代表凑成该钱数使用的最少金币数量
        if (memo[amount] != 0) {
            return memo[amount];
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int res = process2(coins, amount - coins[i]);
            if (res >= 0 && res < min) {
                min = res + 1;
            }
        }
        memo[amount] = min == Integer.MAX_VALUE ? -1 : min;
        return memo[amount];
    }

    /**
     * 改造为动态规划
     * dp数组所代表的就是上面记忆化搜索中memo数组：组成n元所用的最少的金币数量
     */
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        int[] dp = new int[amount + 1];
        //基础数据
        dp[0] = 0;
        //普遍数据
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0 && dp[i - coins[j]] < min) {
                    min = dp[i - coins[j]] + 1;
                }
            }
            dp[i] = min;
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }


    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        LeetCode_322 demo = new LeetCode_322();
        int i = demo.coinChange(coins, 11);
        System.out.println(i);
    }
}
